# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 15/50 粉刷房子
# leetcode第256题（同lcr91题）: https://leetcode.cn/problems/JEj789/description/
# Date: 2024/11/4
from leetcode import test


def minCost_dfs(costs: list[list[int]]) -> int:
    """
    使用dfs算法暴力求解
    """
    n = len(costs)  # 表示房间的个数
    mapping = {}
    if n < 2:
        return min(costs[0])

    def dfs(arr: list[list[int]], start: int, color: int):
        """
        dps 遍历选择树
                    (root)
            0         1        2
          1   2     0   2    0   1
         0 2 0 1   1 2 0 1  1 2 0 2

        :param arr: costs数组
        :param start: 目前遍历的节点
        :param color: 选择的颜色, 使用序号(0,1,2)表示
        :return: 最终的最小花费
        """
        if start >= n:
            return 0

        if mapping.get(str(start) + "-" + str(color)) is not None:
            return mapping.get(str(start) + "-" + str(color))

        # 初始化当前最小成本`
        min_cost = float('inf')

        for i in range(3):
            if i == color:  # 相邻房间之间的颜色不同
                continue
            cost = dfs(arr, start + 1, i) + arr[start][i]
            min_cost = min(min_cost, cost)

        mapping[str(start) + "-" + str(color)] = min_cost
        return min_cost

    return min(dfs(costs, 0, 0), dfs(costs, 0, 1), dfs(costs, 0, 2))


def minCost_dp(costs: list[list[int]]) -> int:
    n = len(costs)
    dp = [[float('inf')] * 3 for _ in range(n)]  # dp[i][j] 表示将第i个房间刷成j颜色的最小成本
    dp[0][0], dp[0][1], dp[0][2] = costs[0][0], costs[0][1], costs[0][2]

    for i in range(1, n):  # 遍历
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                dp[i][j] = min(dp[i][j], dp[i - 1][k] + costs[i][j])

    return int(min(dp[n - 1]))


if __name__ == '__main__':
    costs = [[17, 2, 17],
             [16, 16, 5],
             [14, 3, 19],
             [2, 1, 19]]  # 12
    costs0 = [[7, 6, 2]]  # 2
    costs1 = [[2, 11, 9], [10, 18, 19], [6, 2, 15], [4, 13, 14], [12, 14, 14], [12, 2, 8], [20, 13, 4], [14, 2, 13],
              [4, 4, 18], [20, 19, 3], [20, 2, 8], [2, 5, 6], [16, 1, 1], [10, 12, 12], [9, 6, 20], [14, 9, 19],
              [7, 8, 13], [6, 19, 15], [18, 14, 14], [7, 4, 17], [20, 16, 10], [10, 15, 2]]
    inp = [{"costs": costs}, {"costs": costs0}, {"costs": costs1}, ]
    out = [12, 2, 141]
    test.test_function(minCost_dfs, inp, out)
    test.test_function(minCost_dp, inp, out)
